Python 二分查找之bisect库的使用详解 |
您所在的位置：网站首页 › macbook python文件路径 › Python 二分查找之bisect库的使用详解 |
Python 二分查找之bisect库的使用详解
|
目录简介bisect库的使用bisect_leftbisect_rightinsort_leftinsort_right二分查找基础实现简介bisect库是Python标准库中的一部分，它提供... 目录简介bisect 库的使用bisect_leftbisect_rightinsort_leftinsort_right二分查找基础实现简介bisect 库是 python 标准库中的一部分，它提供了二分查找的功能。二分查找是一种在有序列表中查找某一特定元素的搜索算法。它的时间复杂度为 O ( log n ) O(\log n) O(logn)，比顺序查找的时间复杂度 O ( n ) O(n) O(n) 要有效率。 bisect 库的使用bisect 库提供了 bisect_left、bisect_right、insort_left、insort_right四个函数，用于在有序列表中查找或插入元素。 bisect_leftbisect_left 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，返回该位置，如果元素已经存在，则返回它的左边位置。 函数原型如下： bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)其中，a 是一个有序列表，x 是要查找的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。 示例： # 导入 bisect 库 import bisect # 有序列表 a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10] # 查找元素 4 的位置 print(bisect.bisect_left(a, 4)) # 4 # 查找元素 6 的位置 print(bisect.bisect_left(a, 6)) # 5 bisect_rightbisect_right 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，返回该位置，如果元素已经存在，则返回它的右边位置。 函数原型如下： bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)其中，a 是一个有序列表，x 是要查找的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。 示例： # 导入 bisect 库 import bisect # 有序列表 a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10] # 查找元素 4 的位置 print(bisect.bisect_right(a, 4)) # 4 # 查找元素 6 的位置 print(bisect.bisect_right(a, 6)) # 8除此之外，bisect_right 还可以简写为 bisect ： # 导入 bisect 库 import bisect # 有序列表 a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10] # 查找元素 4 的位置 print(bisect.bisect(a, 4)) # 4 # 查找元素 6 的位置 print(bisect.bisect(a, 6)) # 8 insort_leftinsort_left 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，然后将元素插入该位置，如果元素已经存在，则插入到它的左边位置。 函数原型如下： bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)其中，a 是一个有序列表，x 是要插入的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。 示例： # 导入 bisect 库 import bisect # 有序列表 a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10] # 插入元素 4 bisect.insort_left(a, 4) print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10] # 插入元素 6 bisect.insort_left(a, 6) print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10] insort_rightinsort_right 函数用于在有序列表中二分查找某一位置，使得在该位置插入指定元素后仍保持有序，然后将元素插入该位置，如果元素已经存在，则插入到它的右边位置。 函数原型如下： bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)其中，a 是一个有序列表，x 是要插入的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。 示例： # 导入 bisect 库 import bisect # 有序列表 a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10] # 插入元素 4 bisect.insort_right(a, 4) print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10] # 插入元素 6 bisect.insort_right(a, 6) print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]除此之外，insort_right 还可以简写为 insort ： # 导入 bisect 库 import bisect # 有序列表 a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10] # 插入元素 4 bisect.insort(a, 4) print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10] # 插入元素 6 bisect.insort(a, 6) print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]insort 函数的实质是调用 bisect 函数获取插入位置，然后调用 list.insert 函数将元素插入到该位置。 二分查找基础实现在 Python 中，我们可以使用 bisect 库来实现二分查找，但其只能根据元素的值和元素之间的比较关系来查找元素的位置，如果要根据元素的其他属性或其他关系来查找元素的位置，就需要自己实现二分查找了。 二分查找的基本模板如下： def binary_search(nums, target): left, right = 0, len(nums) - 1 while left = 3存在 i（0 < i < arr.length - 1）使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。 来源：力扣（LeetCode）链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array 解 class Solution: def peakIndexInMountainArray(self, arr: List[int]) -> int: n = len(arr) left, right, ans 编程= 1, n - 2, 0 while left arr[mid + 1]: ans = mid right = mid - 1 else: left = mid + 1 return ans到此这篇关于Python 二分查找：bisect库的使用的文章就介绍到这了,更多相关Python bisect库使用内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以http://www.cppcns.com后多多支持我们！ |
【本文地址】
今日新闻 |
推荐新闻 |